When two parties wish to communicate securely, an efficient mechanism for doing so is the use of a shared secret session key, i.e., a key known only to the two parties that can be used symmetrically to both encrypt and decrypt messages between them for the duration of a communication session. Various methods exist to achieve this, and each have advantages and disadvantages.
Parties can use a trusted key authority that distributes the shared secret key to each of them separately using their unique key encryption key. However, this technique requires the storage of keys—i.e., it is not portable with a user, and if a key encryption key is compromised the system loses its integrity and past communications can be decrypted.
The “Diffie-Hellman” technique, described in U.S. Pat. No. 4,200,770, permits generation of a shared secret key without the use of encryption. Each party generates a large random number. By way of example, party A generates the number X and party B generates the number Y. Each party sends its number through a particular kind of one way function and transmits the output. Only knowledge of one number (X or Y), and the value of the other number sent through the one-way function is sufficient to generate the shared secret key. A drawback of the Diffie-Hellman technique is that each side uses a non-shared random number (X or Y) in independently generating the shared secret key. A result of the use of non-shared random numbers is that each side performs large exponential and modulo calculations when performing one-way functions and generating the shared secret key, resulting in a high computational load on both sides. These calculations are required in order to make it computationally infeasible for an eavesdropper to combine the two-shared numbers in order to obtain the shared secret key.
Variations on the Diffie-Hellman technique exist that attempt to make it more secure. These variations suffer from the same computational burden as the standard Diffie-Hellman technique. For example, U.S. Pat. No. 5,953,424 describes a system with a modification of the key generation technique. In addition to the usual Diffie-Hellman computations on the original numbers (X and Y) and the transmitted numbers (which result from calculations), the '424 patent describes extra factors that may be combined with the standard Diffie-Hellman factors. These factors are not transmitted, so they must be knowable in advance by the communicating parties.
Another variation of the Diffie-Hellman technique is disclosed in U.S. Pat. No. 5,440,635. In this variant, the transmitted numbers are further encrypted using a symmetric key cryptosystem before being transmitted. This doesn't ameliorate any of the disadvantages of Diffie-Hellman, noted above.
A message exchange technique employing a combination of public and private key cryptography to communicate a secret key from one party to another is described in U.S. Pat. No. 5,241,599. The '599 patent requires that each party share knowledge of a secret. A calling party generates a random public key/private key pair, and communicates the public key to the called party using their shared secret. The called party then communicates the secret key to the calling party using both the public key and the shared secret. The technique of the '599 patent suffers from several limitations. The calling party must generate a random public key/private key pair, which is a costly computation that is often preferably performed by the called party. Also, the secret key may be compromised in advance by manipulating the called party to affect the secret key it uses or computes. No manipulation or compromise of the calling party is required.
What is needed is a system and method for establishing secure communication.
The exemplary illustrative non-limiting technology herein provides an encoding protocol for communicating parties to each obtain a shared secret key.
One advantage of the exemplary illustrative non-limiting technology herein is that it is less computationally intensive than previous cryptographic systems to obtain a shared secret key.
Another advantage of the exemplary illustrative non-limiting technology herein is that the calling party is not required to perform any large computations.
Yet another advantage of the exemplary illustrative non-limiting technology herein is that it is highly resistant to attacks, including eavesdropping, impersonating a party, replay attacks, tampering with or probing a party before or after a communications session, and password database hijacking.
Still another advantage of the exemplary illustrative non-limiting technology herein is that it can be used either with or without certificates or physical tokens such as smart cards or biometric devices.
In an exemplary illustrative non-limiting method for obtaining a shared secret key, a party identifies a first shared random number and a second shared random number, and obtains the shared secret key from an output of a combining function having a first input including the first shared random number and having a second input including the second shared random number.
In a further aspect of the exemplary illustrative non-limiting implementation, the shared secret key is used to transform messages.
In another exemplary illustrative non-limiting implementation, a party encodes a first shared random number, decodes a second shared random number, and obtains the shared secret key from an output of a combining function having a first input including the first shared random number and having a second input including the second shared random number.
In a further exemplary illustrative non-limiting implementation, a party encodes a first shared random number and a second key using a first key obtained using information obtained from a password; decodes a second shared random number using a third key; and obtains the shared secret key from an output of a combining function having a first input including the first shared random number and having a second input including the second shared random number.
In a still further exemplary illustrative non-limiting implementation, the second key and the third key form an asymmetric key pair.
In another exemplary illustrative non-limiting implementation, a party decodes a first shared random number, encodes a second shared random number, and obtains the shared secret key from an output of a combining function having a first input including the first shared random number and having a second input including the second shared random number.
In a further exemplary illustrative non-limiting implementation, a party decodes a first shared random number and a second key using a first key obtained from information obtained from a password, encodes a second shared random number using the second key, and obtains the shared secret key from an output of a combining function having a first input including the first shared random number and having a second input including the second shared random number.
In another exemplary illustrative non-limiting implementation, a party communicates a first shared random number and a second shared random number, and obtains the shared secret key from an output of a combining function having a first input including the first shared random number and having a second input including the second shared random number.
In a further exemplary illustrative non-limiting implementation, the party communicates an asymmetric key and a timestamp with the first shared random number, and a timestamp with the second shared random number.
In still another exemplary illustrative non-limiting implementation, a device including at least one processor executes software instructions identifying a first shared random number and a second shared random number, and obtains the shared secret key from an output of a combining function having a first input including said first shared random number and having a second input including said second shared random number.
In yet another exemplary illustrative non-limiting implementation, a machine-readable storage medium contains instructions for a processor, including encoded computer means for identifying a first random number, encoded computer means for identifying a second random number, and encoded computer means for obtaining the shared secret key from an output of a combining function having a first input including said first shared random number and having a second input including said second shared random number.